﻿#pragma once
#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct BinTreeNode {
    ElemType data;
    struct BinTreeNode* lchild;
    struct BinTreeNode* rchild;
} BinTreeNode;



int main() {
    // 假设我们创建了一个简单的二叉树：
    //     A(B(D,E),C())
    BinTreeNode* root = createNode('A');
    root->lchild = createNode('B');
    root->rchild = createNode('C');
    root->lchild->lchild = createNode('D');
    root->lchild->rchild = createNode('E');

    // 输出括号表示
    printBracketRepresentation(root);

    // 执行遍历操作
    printf("Preorder traversal: ");
    preorderTraversal(root);
    printf("\nInorder traversal: ");
    inorderTraversal(root);
    printf("\nPostorder traversal: ");
    postorderTraversal(root);
    printf("\n");

    // 统计叶子节点
    int leavesCount = countLeaves(root);
    printf("Number of leaves: %d\n", leavesCount);

    // 释放二叉树内存
    freeTree(root);

    return 0;
}

// 以下是各个函数的具体实现
BinTreeNode* createNode(ElemType value) {
    BinTreeNode* node = (BinTreeNode*)malloc(sizeof(BinTreeNode));
    node->data = value;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

void preorderTraversal(BinTreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    preorderTraversal(root->lchild);
    preorderTraversal(root->rchild);
}

void inorderTraversal(BinTreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->lchild);
    printf("%c ", root->data);
    inorderTraversal(root->rchild);
}

void postorderTraversal(BinTreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->lchild);
    postorderTraversal(root->rchild);
    printf("%c ", root->data);
}

int countLeaves(BinTreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->lchild == NULL && root->rchild == NULL) {
        return 1;
    }
    return countLeaves(root->lchild) + countLeaves(root->rchild);
}

void freeTree(BinTreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->lchild);
    freeTree(root->rchild);
    free(root);
}

void printBracketRepresentation(BinTreeNode* node) {
    if (node == NULL) {
        printf("()");
    }
    else {
        printf("(%c", node->data);
        if (node->lchild != NULL || node->rchild != NULL) {
            printBracketRepresentation(node->lchild);
            if (node->rchild != NULL) {
                printf(", ");
                printBracketRepresentation(node->rchild);
            }
        }
        printf(")");
    }
}